package com.itheima.leetcode.od.b.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * (B卷,100分)- 乘坐保密电梯（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 有一座保密大楼，你从0楼到达指定楼层m，必须这样的规则乘坐电梯：
 * <p>
 * 给定一个数字序列，每次根据序列中的数字n，上升n层或者下降n层，前后两次的方向必须相反，规定首次的方向向上，自行组织序列的顺序按规定操作到达指定楼层。
 * <p>
 * 求解到达楼层的序列组合，如果不能到达楼层，给出小于该楼层的最近序列组合。
 * <p>
 * 输入描述
 * <p>
 * 第一行：期望的楼层，取值范围[1,50]; 序列总个数，取值范围[1,23]
 * <p>
 * 第二行：序列，每个值取值范围[1,50]
 * <p>
 * 输出描述
 * <p>
 * 能够达到楼层或者小于该楼层最近的序列
 * <p>
 * 备注
 * 操作电梯时不限定楼层范围。
 * 必须对序列中的每个项进行操作，不能只使用一部分。
 * <p>
 * 用例
 * <p>
 * 输入	5 3
 * 1 2 6
 * 输出	6 2 1
 * 说明	1 2 6，6 2 1均为可行解，按先处理大值的原则结果为6 2 1
 * <p>
 * 题目解析
 * <p>
 * 我的解题思路如下：
 * <p>
 * 由于题目说
 * <p>
 * 给定一个数字序列，每次根据序列中的数字n，上升n层或者下降n层，前后两次的方向必须相反，规定首次的方向向上，自行组织序列的顺序按规定操作到达指定楼层
 * <p>
 * 因此，我们可以认为要从数字序列中选出两组数，一组是上升，一组是下降
 * <p>
 * 假设数字序列总个数n，期望楼层是t
 * <p>
 * 如果n是偶数，则上升组要选n/2个，其余的都是下降组
 * 如果n是奇数，则上升组要选n/2+1个，其余的都是下降组
 * 假设数字序列所有元素之和是 sum，而上升组的和upSum，那么下降组的和就是sum - upSum，
 * <p>
 * 如果 upSum - (sum - upSum) <= t，那么当前分组就是一个可能解，而其中sum，t都是已知的，因此可以转化为如下：
 * <p>
 * upSum  <= (sum + t) / 2
 * <p>
 * 即，我们要从给定的数字序列中选择固定数量（n/2或者n/2+1）个，让他的和小于且最接近或等于 (sum + t) / 2。
 * <p>
 * 本题数量级不大，可以当成组合问题求解。
 * <p>
 * 组合求解时，有个难点，那就是我们求解的组合是上升序列，而最终题目要求返回的是整体序列。因此如果求组合，我们只记录上升序列的话，则后期还要过滤剩余的下降序列，然后再将二者进行交叉合并，这就非常麻烦了。
 * <p>
 * 我的思路是，定义一个boolean数组，名字是path，长度和nums相同，如果对应的nums[i]是上升序列的元素，则将path[i] = true。
 * <p>
 * 最后，我们只要根据path即可快速分类出nums中哪些元素是上升序列的，哪些元素是下降序列的。
 * <p>
 * 另外，题目自带用例的说明中提到：
 * <p>
 * 1 2 6，6 2 1均为可行解，按先处理大值的原则结果为6 2 1
 * <p>
 * 貌似是一个组合对应多个排列的情况，这个解决方案是，我们可以在求组合之前，就将nums进行降序，这样先被选进组合的元素必然是大值，因此最后交叉合并的目标序列肯定只会是6 2 1，而不会是1 2 6。
 * <p>
 * 还有一个问题，那就是可能存在多个组合都是最优解的情况，此时我们依旧要按照先处理大值的原则，因此下面代码中我实现了compare方法来从多个最优解中选出先处理大值的。
 */
public class TakeConfidentialElevator {
    public static void main(String[] args) {
        /*//输入处理，这里用了多种方法的输入，大家需要熟悉
        Scanner in = new Scanner(System.in);
        String input_str = in.nextLine();

        String[] tmp2 = input_str.split(" ");
        int[] params = new int[tmp2.length];
        for (int i = 0; i < tmp2.length; i++) {
            params[i] = Integer.parseInt(tmp2[i]);
        }
        int target = params[0];
        int count = params[1];
        int[] nums = Arrays.stream(in.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();*/

        String input1 = "5 3";
        int[] params = Arrays.stream(input1.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();
        int target = params[0];
        int count = params[1];
        List<Integer> floor_list = Arrays.stream("1 2 6".split(" "))
                .map(Integer::parseInt)
                .collect(Collectors.toList());

        System.out.println(getResult(target, count, floor_list));
    }

    /**
     * 组合（回溯）
     *
     * @param target
     * @param count
     * @param floor_list
     * @return
     */
    public static String getResult(int target, int count, List<Integer> floor_list) {
        // 求和
        int sum = floor_list.stream()
                .reduce(Integer::sum)
                .orElse(0);

        int min_distance = Integer.MAX_VALUE;

        //找出下降层数
        List<Integer> downs = new ArrayList<>();
        boolean flag = false;
        solve(target, sum, floor_list, min_distance, count / 2, new ArrayList<>(), 0, downs, flag);

        for (Integer down : downs) {
            if (floor_list.indexOf(down) != -1) {
                floor_list.remove(floor_list.indexOf(down));
            }
        }

        Collections.sort(floor_list, (a, b) -> b - a);
        Collections.sort(downs, (a, b) -> b - a);

        ArrayList<Integer> ans = new ArrayList<>();
        //上升和下降交替存在
        for (int i = 0; i < floor_list.size(); i++) {
            ans.add(floor_list.get(i));
            if (i < downs.size()) {
                ans.add(downs.get(i));
            }
        }

        return ans.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(" "));
    }

    public static void solve(int target, int sum, List<Integer> floor_list, int min_distance, int n,
                             List<Integer> list, int index, List<Integer> downs, boolean flag) {
        // flag 有两个作用
        if (flag) { // 一旦满足条件所有组合停止，如果没有找出所有离得最近的组合（可以借鉴一下思路）
            return;
        }

        if (0 == n) {
            int cnt1 = list.stream()
                    .reduce(Integer::sum)
                    .orElse(0)
                    .intValue();
            int distance = (sum - cnt1) - cnt1;
            int finalDistance = Math.abs(distance - target);
            if (finalDistance == 0) {
                flag = true;
            } else if (min_distance > finalDistance) {
                min_distance = finalDistance;
            }
            downs = new ArrayList<>(list); // flag = false 不断覆盖，一旦为 true 停止覆盖
            return;
        }

        for (int i = index; i < floor_list.size(); i++) {
            list.add(floor_list.get(i));
            solve(target, sum, floor_list, min_distance, n - 1, list, i + 1, downs, flag);
            list.remove(list.size() - 1);
        }
    }
}
